Masala #1188

Xotira 128 MB Vaqt 1000 ms Qiyinchiligi 50 %

3.8 (Baholar 12)

Massivlar soni

Uzunligi $m$ ga teng butun sonlardan iborat $a$ massividagi inversiyalar soni deb quyidagi shartlarni qanoatlantiruvchi $(i, j)$ juftliklar soniga aytiladi:

$1≤i<j≤m$
$a_i >a_j$

Siz $1$ dan $n$ gacha bo‘lgan butun sonlardan tashkil topgan $n$ ta elementli ( $1$ dan $n$ gacha bo‘lgan barcha butun sonlar bir martadan ishtirok etgan) inversiyalar soni $k$ ga teng bo‘lgan massivlar sonini aniqlang. Bu son juda katta bo‘lishi mumkinligi sababli, uni $10^9+7$ ga bo‘lgandagi qoldig‘ini toping.

Kiruvchi ma'lumotlar:

Birinchi qatorda ikkita butun son - $n(1 ≤ n ≤ 1000)$ va $k(0 ≤ k ≤ 10000)$ kiritiladi.

Chiquvchi ma'lumotlar:

Masala javobini $10^9+7$ ga bo'lgandagi qoldig'ini chiqaring.

Misollar

#	input.txt	output.txt
1	10 1	9
2	4 3	6
3	9 13	17957

Izoh:

1-testda mumkin bo'lgan holatlar

1 - (2, 1, 3, 4, 5, 6, 7, 8, 9, 10)

2 - (1, 3, 2, 4, 5, 6, 7, 8, 9, 10)

3 - (1, 2, 4, 3, 5, 6, 7, 8, 9, 10)

4 - (1, 2, 3, 5, 4, 6, 7, 8, 9, 10)

5 - (1, 2, 3, 4, 6, 5, 7, 8, 9, 10)

6 - (1, 2, 3, 4, 5, 7, 6, 8, 9, 10)

7 - (1, 2, 3, 4, 5, 6, 8, 7, 9, 10)

8 - (1, 2, 3, 4, 5, 6, 7, 9, 8, 10)

9 - (1, 2, 3, 4, 5, 6, 7, 8, 10, 9)

Yuqoridagi barcha holatlarda inversiyalar soni 1 ga teng. Osongina ko'rish mumkin-ki boshqa holat mavjud emas.

Telegram Facebook

Yechimini yuborish

Bu amalni bajarish uchun tizimga kiring, agar profilingiz bo'lmasa istalgan payt ro'yxatdan o'tishingiz mumkin